package com.ting.test.algorithms.大厂刷题班;

/**
 * 一个数组 表示每个孩子的得分情况
 * 规定 每个孩子至少有一个糖
 * 如果 右边的孩子分数比左边的高，那么分得的糖也必须比左边的高，
 * 如果分数相同，则不做要求 可以认为没有大小关系，按最少的来
 * 求最少的分配糖果方案
 */
public class 分糖果问题 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 2, 1, 2, 3, 4};
        int count = process(arr);
    }

    private static int process(int[] arr) {
        if (arr == null) {
            return 0;
        }
        int[] left = new int[arr.length];
        left[0] = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }

        int[] right = new int[arr.length];
        right[arr.length - 1] = 1;
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] > arr[i - 1]) {
                right[i] = right[i - 1] + 1;
            } else {
                right[i] = 1;
            }
        }

        int min = 0;
        for (int i = 0; i < arr.length; i++) {
            min += Math.max(left[i], right[i]);
        }
        return min;
    }
}
